package ch09_02;

public class Solution {
    public static long count1(int X, int Y) {
	long[][] dp = new long[X + 1][Y + 1];
	for (int i = 1; i < Y + 1; i++) {
	    dp[0][i] = 1;
	}
	for (int j = 1; j < X + 1; j++) {
	    dp[j][0] = 1;
	}
	for (int i = 1; i < X + 1; i++) {
	    for (int j = 1; j < Y + 1; j++) {
		dp[i][j] = dp[i-1][j] + dp[i][j-1];
	    }
	}
	return dp[X][Y];
    }

    public static long count2(String[] map) {
	int X = map.length - 1;
	int Y = map[0].length() - 1;
	long[][] dp = new long[X + 1][Y + 1];
	for (int i = 1; i < X + 1; i++) {
	    if (map[i].charAt(0) == 'X')
		break;
	    else
		dp[i][0] = 1;
	}

	for (int j = 1; j < Y + 1; j++) {
	    if (map[0].charAt(j) == 'X')
		break;
	    else
		dp[0][j] = 1;
	}

	for (int i = 1; i < X + 1; i++) {
	    for (int j = 1; j < Y + 1; j++) {
		if (map[i].charAt(j) == 'X')
		    continue;
		dp[i][j] = dp[i-1][j] + dp[i][j-1];
	    }
	}
	return dp[X][Y];
    }

    public static void main(String... args) {
	String[] map = {
	    "...X...",
	    "...X...",
	    ".......",
	    "...X..."
	};
	int X = map.length - 1;
	int Y = map[0].length() - 1;
	System.out.println(count1(X, Y));
	System.out.println(count2(map));
    }
}